1. Field of the Invention
The present invention relates to a sequential decoding method. More particularly, the present invention relates to a method for near maximum-likelihood sequential decoding.
2. Description of Related Art
In today's communication industry, convolution code is generally used for preventing channel noises due to its error correction capability. Convolution code is usually expressed as (n,k,m), that is, each k-bit data block is encoded into an n-bit codeword to be output, and m is a memory length which refers to a number of registers used for encoding. Thus, besides according to the k-bit data block, the encoded n-bit codeword is also related to previous m k-bit data blocks, and the error correction capability of the convolution code is in direct ratio to m.
The encoded n-bit code-words is further related to previous data blocks besides being related to the inputted k-bit data block. Thus, convolution code may also use the previous status and the inputted k-bit data block for outputting the n-bit codeword. Accordingly a trellis diagram is always applied to encoding convolution code for obtaining the statuses and paths that a message sequence will pass through while encoding the message sequence and the n-bit codewords corresponding each path.
FIG. 1 illustrates a trellis diagram of convolution code (3,1,2). In FIG. 1, the length L of the data sequence is assumed to be L=4, that is, every time 4 data blocks are inputted. FIG. 1 illustrates nodes and the paths corresponding to the nodes. Each node is denoted as l−s, wherein l represents level, and lε{0, 1, 2, 3, 4, 5, 6}; s represents status, and sε{0, 1, 2, 3}. The paths starting off from each node represent the 3-bit codewords to be output. When l=0˜4, two paths start off from each node, the path on top is taken when the data block is 1, and the path below is taken when the data block is 0. Thus, each data block in the inputted message sequence selects the path it will take from the origin node (0-0) to the goal node (6-0), accordingly the codewords to be output are determined.
The methods usually used for decoding convolution code are viterbi decoding and sequential decoding. Wherein, according to viterbi decoding, the metrics of the received sequence and all the possible paths in the trellis diagram are calculated to determine a path having the smallest metric, and the originally transmitted message sequence can be obtained from this path. However, in viterbi decoding, the decision of selecting an existent path has to be made at every status, thus viterbi decoding method presents as the optimum decoding method. However, in actual application, the quantity of calculation or the hardware complexity is in exponential direct ratio to memory length m, thus, viterbi decoding is only suitable for convolution code with shorter memory length. Moreover, since the error correction capability of convolution code is in direct ratio to m, the error correction capability of convolution code can not be fully utilized if viterbi decoding is adopted.
Another decoding method for convolution code is sequential decoding, which is operated in tree diagram, and Fano metric is used for calculating the relationship between the received sequence and possible codewords. Although the calculation quantity and the hardware complexity of sequential decoding method does not grows exponentially to the memory length m, maximum-likelihood decoding cannot be accomplished by sequential decoding, thus, sequential decoding is the sub-optimum decoding in performance.
Yunghsiang S. Han, Po-Ning Chen, and Hong-Bin Wu published an article with title “A Maximum-Likelihood Soft-Decision Sequential Decoding Algorithm for Binary Convolutional Codes” in “Transactions on communications” VOL. 50, No. 2 issued by IEEE (Institute of Electrical and Electronic Engineers) on February, 2002, wherein a method for maximum-likelihood sequential decoding was disclosed and a new metric was provided to replace Fano metric, according to this method, maximum-likelihood decoding can be accomplished by sequential decoding as viterbi decoding performs optimum decoding. Moreover, the new metric cannot be negative, which allows sequential decoding to be operated in trellis diagram.